Fault tolerant circuit design is becoming increasingly important as integrated circuits and computer chips become more complex and more expensive to fabricate.
The effect of a defective gate detected during fabrication is the scrapping of the chip. A defective gate in a hostile environment, where repair is impossible or impractical or in a critical application, can result in a catastrophe, for example, in outer space or in a life-support system.
Fault-tolerant design, in general, is known. In some instances redundant gates and circuits arc added to the circuit &sign layout. The addition of redundancy results in a portion of the chip or wafer area being used for redundant circuits rather than being used for additional circuits. Such results are undesirable and inefficient due to the wafer area overhead costs.
Fault tolerant gate circuits are described in an article by D. Kleitman et al entitled "On the Design of Reliable Boolean Circuits that Contain Partially Unreliable Gates" in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Nov. 20-22, 1994, pages 332-346. Designs for k-fault tolerant gate circuits, where k is 2.sup.n -1 for n&gt;0, are disclosed. A simple fault tolerant design comprising three gates, which design may be iteratively repeated for k-fault tolerant designs, is described. As is often the situation, after a relatively low value of k, for example three-fault tolerant design, the quantity of gates required for implementation of the fault tolerant design becomes an important consideration. As the quantity of additional gates required increases, the circuit reliability decreases and the chip area required for the additional gates increase. The iteratively repeated embodiment does not necessarily yield an optimal result for k greater than about three.